package merge;

public class MergeExample {
    /**
     * 对数组的left至right这部分进行排序
     * @param  nums
     * @param  left
     * @param  right
     */
    public static void sort(int[] nums, int left, int right){
        if(left == right) return;
        int mid = left + (right - left)/2;
        sort(nums, left, mid);//对数组的左半部分排序
        sort(nums, mid+1, right);//对数组的右半部分排序
        merge(nums, left, mid+1, right);//合并数组的两半部分
    }

    /**
     * 合并数组的任意两半部分（均有序）
     * @param  nums
     */
    private static void merge(int[] nums, int left, int mid, int right){

        int[] result = new int[right - left + 1];

        int i = left, j = mid;
        int k = 0;
        while(i < mid && j <= right){
            if(nums[i] <= nums[j]){
                result[k++] = nums[i++];
            }else result[k++] = nums[j++];
        }

        while(i < mid){
            result[k++] = nums[i++];
        }

        while(j <= right){
            result[k++] = nums[j++];
        }

        k = 0;
        for(i = left; i <= right; i++){
            nums[i] = result[k++];
        }
    }
}
